import numpy as np


class AstarSearch:
	__close_list = __close_set = []
	__open_list = __fringe = []
	__INF = 10000

	def __init__(self):
		pass

	def __init(self, dis, h, start, goal, name=None):
		self.__dis = dis
		self.__h = h
		self.__name = name
		self.__start = start
		self.__goal = goal
		self.__NODE_SIZE = len(dis)
		self.__route = np.array([0] * self.__NODE_SIZE)
		self.__g = np.array([self.__INF] * self.__NODE_SIZE)

	def __name_of(self, node):
		try:
			return self.__name[node]
		except Exception:
			return node

	def __print_route(self, now):
		if (now == self.__start):
			print("%s->" % self.__name_of(now), end='')
			return
		self.__print_route(self.__route[now])
		if (now == self.__goal):
			print("%s . The cost is %d" % (self.__name_of(now), self.__g[self.__goal]))
		else:
			print("%s->" % self.__name_of(now), end='')

	def __best_in_the_open_list(self):
		minn = self.__INF
		min_i = 0
		for i in self.__open_list:
			if (self.__g[i] + self.__h[i] < minn):
				minn = self.__g[i] + self.__h[i]
				min_i = i
		return min_i

	def astarSearch(self, dis, h, start, goal, name=None):
		self.__init(dis, h, start, goal, name)
		self.__g[start] = 0
		self.__open_list.append(start)
		while (len(self.__open_list) != 0):
			now = self.__best_in_the_open_list()
			for i in range(0, self.__NODE_SIZE, 1):
				if (i == now or dis[now][i] >= self.__INF or i in self.__close_list):
					continue
				if (self.__g[i] > self.__g[now] + dis[i][now]):
					if (i not in self.__open_list):
						self.__open_list.append(i)
					self.__route[i] = now
					self.__g[i] = self.__g[now] + dis[i][now]
			self.__open_list.remove(now)
			if (now == goal):
				self.__print_route(now)
				return True
			self.__close_list.append(now)
		print("No solution found!")
		return False
